package _02_第二季.排序;

import java.util.Arrays;

/*
    归并排序,本质上一个二叉树的后序遍历,不断将数组化成子数组进行排序，最后不断地进行合并
 */
public class Merge {
    private static int[] temp;

    public static void sort(int[] nums){
        if(nums == null || nums.length == 0) return;
        temp = new int[nums.length];

        sort(nums,0,nums.length - 1);
    }

    public static void sort(int[] nums,int lo,int hi){
        if(lo >= hi) return;

        int mid = lo + (hi - lo) / 2;

        sort(nums,lo,mid);
        sort(nums,mid+1,hi);

        merge(nums,lo,mid,hi);
    }

    public static void merge(int[] nums,int lo,int mid,int hi){
        for(int i=lo;i<=hi;i++){
            temp[i] = nums[i];
        }

        int i = lo,j = mid + 1;
        for(int p=lo;p<=hi;p++){
            if(i == mid + 1){
                nums[p] = temp[j++];
            }else if(j == hi + 1){
                nums[p] = temp[i++];
            }else if(temp[i]>temp[j]){
                nums[p] = temp[j++];
            }else{
                nums[p] = temp[i++];
            }
        }
    }

    public static void main(String[] args) {
        int[] nums = {2,1,50,25,3,65,41,78,23,6,99,50,450,69};
        sort(nums);
        System.out.println(Arrays.toString(nums));
    }
}
